{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementation of a Graph as an Adjacency List\n",
    "\n",
    "\n",
    "Using dictionaries, it is easy to implement the adjacency list in Python. In our implementation of the Graph abstract data type we will create two classes: **Graph**, which holds the master list of vertices, and **Vertex**, which will represent each vertex in the graph.\n",
    "\n",
    "Each Vertex uses a dictionary to keep track of the vertices to which it is connected, and the weight of each edge. This dictionary is called **connectedTo**. The constructor simply initializes the id, which will typically be a string, and the **connectedTo** dictionary. The **addNeighbor** method is used add a connection from this vertex to another. The **getConnections** method returns all of the vertices in the adjacency list, as represented by the **connectedTo** instance variable. The **getWeight** method returns the weight of the edge from this vertex to the vertex passed as a parameter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Vertex:\n",
    "    def __init__(self,key):\n",
    "        self.id = key\n",
    "        self.connectedTo = {}\n",
    "\n",
    "    def addNeighbor(self,nbr,weight=0):\n",
    "        self.connectedTo[nbr] = weight\n",
    "\n",
    "    def __str__(self):\n",
    "        return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])\n",
    "\n",
    "    def getConnections(self):\n",
    "        return self.connectedTo.keys()\n",
    "\n",
    "    def getId(self):\n",
    "        return self.id\n",
    "\n",
    "    def getWeight(self,nbr):\n",
    "        return self.connectedTo[nbr]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "In order to implement a Graph as an Adjacency List what we need to do is define the methods our Adjacency List object will have:\n",
    "\n",
    "* **Graph()** creates a new, empty graph.\n",
    "* **addVertex(vert)** adds an instance of Vertex to the graph.\n",
    "* **addEdge(fromVert, toVert)** Adds a new, directed edge to the graph that connects two vertices.\n",
    "* **addEdge(fromVert, toVert, weight)** Adds a new, weighted, directed edge to the graph that connects two vertices.\n",
    "* **getVertex(vertKey)** finds the vertex in the graph named vertKey.\n",
    "* **getVertices()** returns the list of all vertices in the graph. \n",
    "* **in** returns True for a statement of the form vertex in graph, if the given vertex is in the graph, False otherwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Graph:\n",
    "    def __init__(self):\n",
    "        self.vertList = {}\n",
    "        self.numVertices = 0\n",
    "\n",
    "    def addVertex(self,key):\n",
    "        self.numVertices = self.numVertices + 1\n",
    "        newVertex = Vertex(key)\n",
    "        self.vertList[key] = newVertex\n",
    "        return newVertex\n",
    "\n",
    "    def getVertex(self,n):\n",
    "        if n in self.vertList:\n",
    "            return self.vertList[n]\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "    def __contains__(self,n):\n",
    "        return n in self.vertList\n",
    "\n",
    "    def addEdge(self,f,t,cost=0):\n",
    "        if f not in self.vertList:\n",
    "            nv = self.addVertex(f)\n",
    "        if t not in self.vertList:\n",
    "            nv = self.addVertex(t)\n",
    "        self.vertList[f].addNeighbor(self.vertList[t], cost)\n",
    "\n",
    "    def getVertices(self):\n",
    "        return self.vertList.keys()\n",
    "\n",
    "    def __iter__(self):\n",
    "        return iter(self.vertList.values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see a simple example of how to use this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "g = Graph()\n",
    "for i in range(6):\n",
    "    g.addVertex(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: <__main__.Vertex instance at 0x10476b680>,\n",
       " 1: <__main__.Vertex instance at 0x104cce5f0>,\n",
       " 2: <__main__.Vertex instance at 0x10395d950>,\n",
       " 3: <__main__.Vertex instance at 0x1039c00e0>,\n",
       " 4: <__main__.Vertex instance at 0x1039c4e60>,\n",
       " 5: <__main__.Vertex instance at 0x1039c45f0>}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g.vertList"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "g.addEdge(0,1,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 connectedTo: [1]\n",
      "[<__main__.Vertex instance at 0x104cce5f0>]\n",
      "\n",
      "\n",
      "1 connectedTo: []\n",
      "[]\n",
      "\n",
      "\n",
      "2 connectedTo: []\n",
      "[]\n",
      "\n",
      "\n",
      "3 connectedTo: []\n",
      "[]\n",
      "\n",
      "\n",
      "4 connectedTo: []\n",
      "[]\n",
      "\n",
      "\n",
      "5 connectedTo: []\n",
      "[]\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for vertex in g:\n",
    "    print vertex\n",
    "    print vertex.getConnections()\n",
    "    print '\\n'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Great Job!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
